package org.example;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Test2 {
    //leetcode 串联所有单词的子串
    //https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150

    /**
     * 滑动窗口，指针每次移动的个数为words中每个单词的长度
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String,Integer> hash1 = new HashMap<>();
        for (String ss : words) {
            hash1.put(ss,hash1.getOrDefault(ss,0) + 1);
        }
        int len1 = words.length, len2 = words[0].length();
        List<Integer> ret = new ArrayList<>();
        //barfoothefoobarman
        //也就相当于，帮字符串分为了跟words中每个单词相同长度的单词
        //bar foo the...
        //那么使之成立的情况肯恶搞不是这样分的，也可能是b arf oot...
        //所以第一个循环就是进行滑动窗口的次数
        for (int i = 0; i < len2; i++) {
            //hash2用来记录一次滑动窗口中窗口中单词的个数，这个包括有效单词和无效单词个数
            Map<String,Integer> hash2 = new HashMap<>();
            for (int left = i, right = i, count = 0; right + len2 <= s.length(); right += len2) {
                //进窗口
                String in = s.substring(right,right + len2);
                hash2.put(in,hash2.getOrDefault(in,0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in,0)) count++;
                //判断
                if (right - left + 1 > len1 * len2) {
                    String out = s.substring(left,left + len2);
                    if (hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out) - 1);
                    left += len2;
                }
                if (count == len1) ret.add(left);
            }
        }
        return ret;
    }
}
